LP Opt

• Flow

  Ford-fulkerson: $O(fE)$, 구현이 간결하지만 복잡도에 유량상한 f가 들어가기 때문에, 유량이 클수록 느려지며, 유량은 입력의 크기와 독립적이기때문에 문제에 따라 얼마든지 느려질 수 있다.

  Dinitz: $O(V^2E)$, 많은경우 복잡도보다 상당히 빠르게 동작하며 특히 이분매칭에선 O(EV^0.5)로 상한이 줄어들지만 어쨌든 복잡도가 Subquadratic보다는 훨씬 크다.

• Mincost Flow

  SPFA가 저격데이터를 만들 수 있지만 플로우그래프로 저격하기는 쉽지 않으므로 사실상 O(fE)복잡도에 동작하도록 하는 코드가 많이 쓰인다. 음수사이클이 없는 residual graph는 potential개념을 사용해서 다익스트라를 돌릴 수 있다고 한다. 이름이 아마 Johnson's Algorithm이었나 그럴것이다.

• Matching

• Bipartie Graph

• Shortest Path

• etc

  Push-relabel과 Cost scaling flow등 온갖 괴상한것들이 많은데 잘 모르겠다. 아주 최근엔 O(E^(1+o(1))) 플로우알고리즘이 나왔다고함.

LP Dual Optimization

• BOJ 1281 보석상

  LP식 세우고 Dual하면 가중치최대이분매칭 LP식이 나옴

Convex DP Optimization

• Buy Low Sell High

  slope trick, weighted non-bipartite matching

  Slope Trick 유형4 문제이다. 이 문제는 크게 2가지접근이 있는데, 하나는 슬로프트릭의 그래프개형분석이고, 하나는 (call/put)option접근법이다. 이중에 옵션접근법이 flow의 residual과 동일한 개념인것을 깨달았다. Buy low sell high를 플로우로 모델링하기전에, 각 날짜에 Buy/None/Sell 3가지 행동을 정하면 Buy와 그 오른쪽Sell을 매칭하는 문제가 된다. 오른쪽에 매칭한다는게 거슬리는데, 일반매칭으로 생각해도 되는게 아무 매칭이나 잡아도 그 매칭의 두 정점 순서가 항상 왼->오 로 나뉘니까 가중치는 유일하게 결정되서 상관없다. USACO-Landscaping(BOJ12010)의 공식해설의 stack스러운 매칭과 KOI-소방차(BOJ2586)의 풀이에 등장하는 stack스러운 매칭을 생각해보면, 어떤 매칭이던 그 값과 동일하면서 교차하지 않는 매칭으로 변형이 가능하다. 교차는 그렇다치고 값이 동일한 이유는 전체 매칭비용이 (Sell합-Buy합)으로 순서에 불변임을 생각하면 자명하다. 이제 그러한 매칭에서 판매는 그 이전들의 가능한 구매중 최적인걸 그때그때 매칭해주면 되고, 각인덱스에서 Buy/None/Sell이 고정되있다면 이대로 충분하지만 그게 아니므로 지금 판매한다고 가정하고 매칭하고 이후에 지금판매하지 않는 (=구매하거나 아무것도 안함) 즉, 매칭을 취소할 수 있는 option?residual?을 선택지에 추가해주면 된다. https://codeforces.com/contest/866/submission/141353687 이 코드를 보자. 루프돌면서 i옵션을 획득하고, 지금까지의 옵션중에 최적인것과 현재것을 매칭시킨 이후, i+1에선 {i와 매칭한 j(<i) 이전의 남은 옵션들}+{i와 매칭} 이란 옵션만 남게된다. 이래도 괜찮은 이유는 매칭이 스택형태로 됨을 위에서 보였기 때문에, 항상 매칭시 내부원소끼리 매칭되므로, j와 i를 매칭시켰을때 [j+1,i)의 옵션은 i+1을 처리할 때 볼 필요가 없다. j가 i에 매칭하는것보다 i+1에 매칭하는게 최적인지만 살펴보면 그 사이것들은 안봐도 충분하다는 것이다. 그래서 저런 코드가 잘 작동하는것이다. j와 매칭된걸 취소하고 i+1과 매칭하는것은 residual경로이고, j이전옵션들과 매칭하는건 일반경로이거나 그 이전에 추가된 residual경로일 것이다. 아무튼 플로우에서도 residual경로도 augment경로 구할때 일반경로와 완전히 구분없이 사용하기 때문에 처음추가된 옵션이나 매칭후 residual로 추가된 옵션이나 동일하게 관리해줄 수 있다.

• APIO 2007 백업 (BOJ1150)

  alien trick, weighted non-bipartite matching

  매칭비용은 두 매칭위치의 "거리"이고, 비용을 최소화해야하며, 매칭개수제한 k가 추가되었다. 위 Buy Low Sell High와 다른점은 비용이 거리라서 단순히 차이가 아니다. 위 문제에선 매칭의 비용이 (인덱스오른쪽인것의 값 - 인덱스 왼쪽인것의 값) 이었다면, 이 문제에선 max(val1,val2)-min(val1,val2) 혹은 |val2-val1|정도로 표현할 수 있겠다. 즉, 위 문제는 인덱스가 영향이 있고, 이 문제는 거리라서 매칭시 인덱스는 의미가 없다. 아무튼 임의의 매칭을 선택시 비용이 유일하게 결정되긴 함은 알 수 있다. 임의의 매칭을 같거나 더 적은비용의 교차하지 않는 매칭으로 변경가능한가? 거리라서 가능한듯. 거리 오름차순으로 정렬후 인접2개씩 매칭하면 되니까. 구현좀 더러운 residual개념의 PQ그리디가 되는것 같고, 다음 글들에 따르면 Alien Trick도 가능하다는것 같다. https://codeforces.com/blog/entry/58888?locale=ru https://www.jurnalgalang.com/2019/01/monge-property-binary-search.html

• KOI 2005 소방차 (BOJ2586), USACO Open 2016 Landscaping (BOJ12010)

  Slope Trick, weighted bipartite matching

  두 문제 다 아직 안(못?)풀었고, USACO공식해설의 스택매칭+그리디풀이는 알고있다. Bipartite의 두 그룹을 A,B라고 할때 stack스런 매칭을 떠올려보면 각 레벨에선 A와B가 altering하는것을 관찰할 수 있고, 그래서 레벨별로 짝수개이면 완전매칭이 최적이고, 홀수개이면 하나를 제거한 나머지 매칭중 최대를 찾으면 된다. 알려진 dp optimization적인 관점의 해석은 아직 생각안나지만 USACO Guide의 Slope Trick예제로 사용되었으니 Slope Trick으로 생각할 수 있나보다.

Sublinear Augment Path

MCMF로 모델링했을때, 그래프가 단순해서 최단경로를 O(E)보다 빠르게 O(logE)정도에 구할 수 있는 문제들이다. MCMF라는점에서 볼록성이 따라오기 때문에 매개변수화하면 그리디가 좀 더 쉬워지기도 하는것 같다. 뭐 아무튼 구현량을 논외로하면 MCMF의 최단경로를 분해해서 관리해주는 방법이 제일 직관적인거같다.

• 5896 효율적으로 소 사기

  N마리의 소와 2개의 가격을 N:2로 K(n,2)완전이분그래프로 그리면 유량f(=구매개수)의 최소비용을 구할 수 있다. 가중치는 (src:N)=1, (N:2)=정가&할인가, (2:snk)=(할인그룹은 쿠폰개수,정가그룹은 N)으로 주면 된다. AC코드를보면 정렬해서 소 하나씩 추가해보면서 비용제한 맞췄을때 최대갯수를 구하는 방식이다. 방금 만든 그래프에서 최단경로로 플로우1씩 흘려보내는게 소 하나 추가해보는것과 동치일듯? 정리하기 귀찮아서 더 보고싶다면 내가 45308987번 제출에 했던 메모를 보자.

• 11848 Schools

  위 문제와 동일하게 모델링할 수 있고, 비용제한이 없으므로 더 쉽다고 봐야할듯? 비용제한이 없는 대신 두 그룹의 개수제약이 걸려있어서 그게 그거다. 이것도 마찬가지로 더 자세한내용은 제출한 코드 주석을 읽자.

• 17169 Eat Economically

  Schools의 코드를 좀만 수정해서 냈다가 틀렸다. Schools에 짠 코드는 residual의 residual을 타는 경우가 없는데, 여기서는 유량을 여러번흘려야해서 그런경우가 존재한다. residualAB를 사용할때 residualBA에 추가해주는 간단한 수정을 해야하고, 저런케이스가 생겨서 최단경로를 케웍으로 찾는게 불가능해서 4가지케이스의 값을 확실하게 비교한 다음 최소인거로 진행해주도록 수정하면 된다. 위의 구현들이 점차 발전해서 이 문제의 General한 로직까지 올 수 있었으니, 다음에 비슷한 풀이 필요하면 이걸 base로 짜면 될거같다.

• 21916 Neo-Robin Hood

  -

• 20370 공정한 게임

  -

• -

이 글에서는 다양한 LP문제들을 최적화하는 테크닉들을 정리한다.

일단 플로우와 최단경로의 LP표현은 다음과 같다. WIP

(Mincost)Flow로 모델링한 이후 그래프의 특징을 관찰하여 최적화하는 문제들이 많이 있다. WIP

문제의 개수제약(money 제약?)을 무시하고 뭔가 일단 해보는건 뭔가 dual simplex의 프로세스와 비슷한 느낌이 드는데 연관성이 있을듯. 옵션개념도 플로우의 residual추가하는것과 동치인거같다. convex dp optimization: 모든 convexity는 mcmf로 증명이 된다는걸 구사과블로그에서 본것같은데 정확힌 모르겠다.

NEERC Mole Tunnels